#ifndef _BNB_H
#define _BNB_H


#include "../lib/common.h"
#include "../lib/compare.h"


#define ACTV_NODES_SIZE 10000   /**< tamanho de um bloco a ser considerado */
#define DEBUG 0                 /**< modo debug */



/** Constroi o vetor com a permutacao dada pela indexacao dos jobs
 *
 * @param index Vetor de indexacao dos jobs
 * @param n Total de jobs indexadas
 * @param nJobs Total de jobs
 *
 * @return Vetor com a permutacao
 */
int* setPerm(const int *index, const int n, const int nJobs);


/** Funcao que imprime o conteudo de um no
 * @param nd Ponteiro do no
 * @param nJobs Total de jobs
 */
void printNode(const Node *nd, const int nJobs);


/** Imprime a fila de prioridade
 * @param queue Vetor contendo a fila
 * @param qSize Tamanho da fila (excluindo o indice 0)
 * @param nJobs Total de jobs
 */
void printQueue(const Node **queue, const int qSize, const int nJobs);


/** Libera a memoria de um no
 * @param nd No a ser liberado
 */
void freeNode(Node *nd);


/** Calcula o lower bound do no
 * @param nd No a ser calculado
 * @param jobs Vetor contendo os jobs
 * @param jobsSortT1 Vetor contendo os jobs ordenados por (task1, task2)
 * @param jobsSortT2 Vetor contendo os jobs ordenados por (task2, task1)
 * @param nJobs Total de jobs
 */
int calcLowBound(const Node *nd, const Job *jobs,
        const Job *jobsSortT1, const Job *jobsSortT2, const int nJobs);


/** Cria o primeiro no do conjunto (problema original)
 * @param jobs Vetor contendo os jobs
 * @param nJobs Total de jobs
 * @return Ponteiro para o no criado
 */
Node* generateFirstNode(const Job *jobs, const int nJobs);


/** Determina a solucao padrao
 * @param jobs Vetor contendo os jobs
 * @param nJobs Total de jobs
 * @return Ponteiro para o no contendo a solucao
 */
Node* generateDefaultSolution(const Job *jobs, const int nJobs);


/** Gera um filho incluindo o job dado no fim
 *
 * @param parent Node pai
 * @param nextJob Index do job seguinte
 * @param id ID para o novo no
 * @param nJobs Total de jobs
 * @param jobs Vetor contendo os jobs
 * @param jobsSortT1 Vetor contendo os jobs ordenados por (task1, task2)
 * @param jobsSortT2 Vetor contendo os jobs ordenados por (task2, task1)
 *
 * @return Node filho gerado
 */
Node* generateChild(const Node *parent, const int nextJob, const int id, const int nJobs,
        const Job *jobs, const Job *jobsSortT1, const Job *jobsSortT2);


/** Funcao que verifica se duas schedules contem os mesmos jobs
 * @param a Primeira schedule
 * @param b Segunda schedule
 * @param nJobs Total de jobs
 * @return
 *      - 1: iguais
 *      - 0: diferentes
 */
int sameSched(const int *a, const int *b, const int nJobs);


/** Funcao que verifica a dominancia de um dado node
 * @param nd Node a ser verificado
 * @param actvNodes Vetor de nos ativos
 * @param nActvNodes Endereco do total de nos ativos
 * @param nJobs Total de jobs
 * @return
 *      - 1: existe no dominante
 *      - 0: nao existe no dominante
 */
int verificaDominante(const Node *nd, Node **actvNodes, int *nActvNodes, const int nJobs);


/** Funcao que resolve o FSP por BnB
 * 
 * @param jobs Vetor contendo os jobs
 * @param nJobs Total de jobs
 * @param maxExecTime Tempo maximo de execucao (em segundos)
 * @param maxNodes Numero maximo de nos explorados
 *
 * @return Solution contendo a melhor solucao encontrada
 */
Solution* bnb(const Job *jobs, const int nJobs, const int maxExecTime, const int maxNodes);


/** Verifica a melhor solucao encontrada
 * @param ans Solution a ser formulada
 * @param bestSol Melhor solucao encontrada
 * @param branchNode No ativo com menor lower bound
 * @param jobs Vetor contendo os jobs
 * @param nJobs Total de jobs
 * @param maxExecTime Tempo maximo de execucao (em segundos)
 */
void buildAnswer(Solution *ans, Node *bestSol, Node *branchNode,
        const Job *jobs, const int nJobs, const int maxExecTime);


/** Funcao principal
 * @param argc Total de argumentos
 * @param argv Vetor de string dos argumentos
 *
 * @return
 *      - EXIT_SUCCESS: saida com sucesso
 *      - EXIT_FAILURE: saida com erro
 */
int main(int argc, const char *argv[]);


#endif

